// https://www.lintcode.com/problem/zombie-in-matrix/description

class Solution {
public:
    /**
     * @param grid: a 2D integer grid
     * @return: an integer
     */
    struct Node
    {
        int x;
        int y;
        int dis;
    };
    
    int zombie(vector<vector<int>> &grid) {
        queue<Node> q;
        int m = grid.size();
        int n = grid[0].size();
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == 1)
                {
                    q.push(Node{i, j, 0});
                }
            }
        }
        int dx[4] = {-1, 0, 1, 0};
        int dy[4] = {0, 1, 0, -1};
        int max_dis = 0;
        while (!q.empty())
        {
            Node node = q.front();
            q.pop();
            for (int i = 0; i < 4; ++i)
            {
                int nx = node.x + dx[i];
                int ny = node.y + dy[i];
                max_dis = node.dis; //不需要比较
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 0)
                {
                    grid[nx][ny] = 1;
                    q.push(Node{nx, ny, node.dis + 1});
                }
            }
        }
        for (int i = 0; i < m; ++i)
        {
            for (int j = 0; j < n; ++j)
            {
                if (grid[i][j] == 0)
                {
                    return -1;
                }
            }
        }
        return max_dis;
    }
};